package demo1;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //合并区间
    public int[][] merge(int[][] intervals) {
        int n = intervals.length;
        Arrays.sort(intervals,(i,j)->{
            return i[0] - j[0];
        });
        ArrayList<int[]> list = new ArrayList<>();
        for (int i = 0; i < n; ) {
            int[] nums = new int[2];
            nums[0] = intervals[i][0];
            nums[1] = intervals[i][1];
            int j = 0;
            for ( j = i; j < n-1; j++) {
                if(nums[1]>=intervals[j+1][0]){
                    nums[1] = Math.max(nums[1],intervals[j+1][1]);
                }else break;
            }
            i = j+1;
            list.add(nums);
        }
        return list.toArray(new int[0][2]);
    }

    //坏了的计算器
    public int brokenCalc(int startValue, int target) {
        int count = 0;
        while (true) {
            if(target>startValue) {
                if (target % 2 == 1) {
                    target++;
                    count++;
                } else {
                    target /= 2;
                    count++;
                }
            }else if(target<startValue){
                count += startValue-target;
                target = startValue;
            }else break;
        }
        return count;
    }

    public static void main1(String[] args) {
        monotoneIncreasingDigits(1234);
    }

    //单调递增的数字
    public static int monotoneIncreasingDigits(int n) {
        String str = Integer.toString(n);
        char[] nums = str.toCharArray();
        int len = nums.length;
        for (int i = 0; i < len-1; i++) {
            if(nums[i]>nums[i+1]){
                while(i-1>=0 && nums[i-1] == nums[i])
                    i--;
                nums[i]--;
                for (int j = i+1; j < len; j++) {
                    nums[j] = '9';
                }
                return Integer.parseInt(new String(nums));
            }
        }
        return n;
    }

    //加油站
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            int step = 0;
            for(;step<n;step++){
                int index = (i+step)%n;
                sum += gas[index];
                sum -= cost[index];
                if(sum<0) break;
            }
            if(sum>=0) {
                return i;
            }
            i = i+step;
        }
        return -1;
    }
}
